////////////////////////////////////////////////////////////////////////////
//
//  Crytek Engine Source File.
//  Copyright (C), Crytek Studios, 2010.
// -------------------------------------------------------------------------
//  File name:   CWBufferCuller.cpp
//  Version:     v1.00
//  Created:     32/05/2010 by Peter Bajusz.
//  Compilers:   Visual Studio.NET
//  Description: Occlusion Culler using software WBuffer rendering
// -------------------------------------------------------------------------
//  History:
//
////////////////////////////////////////////////////////////////////////////
#include "StdAfx.h"
#if OCCLUSIONCULLER == CWBufferCuller

#if defined(WIN32) || defined(gringo)

#define OC_SSE 1

#include "CWBufferCuller.h"

#define PROJECT_VERTEX(p, v)															\
{																													\
	float rhw = 1.0f/v.z;																		\
	p.x = (.5f*m_Width ) + v.x*rhw * (.5f*m_Width ) - .5f;	\
	p.y = (.5f*m_Height) + v.y*rhw * (.5f*m_Height) - .5f;	\
	p.z = rhw;																							\
}

#define BOX_EPSILON 0.01f		// 1 cm in world space

#define COVERAGE_DEBUG_RECTANGLE_SCALE 0.8f

#define BLOCK_SHIFT	3
#define BLOCK_SIZE	(1<<BLOCK_SHIFT)
#if (2 != BLOCK_SHIFT) && (3 != BLOCK_SHIFT)
#error BLOCK_SHIFT can be 2 or 3
#endif

CWBufferCuller::CWBufferCuller()
{
	InitStats();

	m_Width = 0;
	m_Height = 0;
	m_Buffer = NULL;
	m_SuperWidth = 0;
	m_SuperHeight = 0;
	m_SuperBuffer = NULL;
	m_DebugBuffer = NULL;
	m_DebugTextureID = -1;
}

CWBufferCuller::~CWBufferCuller()
{
	FreeBuffers();
}

void CWBufferCuller::InitStats()
{
	m_FrameTime	=	0;
	m_TrisWritten = 0;
	m_ObjectsWritten = 0;
	m_TrisTested = 0;
	m_ObjectsTested = 0;
	m_ObjectsTestedAndRejected = 0;
}

void CWBufferCuller::FreeBuffers()
{
	_aligned_free(m_Buffer);
	m_Buffer = NULL;
	SAFE_DELETE_ARRAY(m_DebugBuffer);
	SAFE_DELETE_ARRAY(m_SuperBuffer);
	if (-1 != m_DebugTextureID)
	{
		m_pRenderer->RemoveTexture(m_DebugTextureID);
		m_DebugTextureID = -1;
	}
}

void CWBufferCuller::BeginFrame(const CCamera &rCam)
{
	FUNCTION_PROFILER_3DENGINE;

	InitStats();
	m_Camera = rCam;

	int height = min(max(1, GetCVars()->e_CoverageBufferResolution), 256);
	height = (height + (BLOCK_SIZE-1)) & ~(BLOCK_SIZE-1);
	int width = height * m_Camera.GetViewSurfaceX() / m_Camera.GetViewSurfaceZ();
	width = (width + (BLOCK_SIZE-1)) & ~(BLOCK_SIZE-1);
	
	if (height != m_Height || width != m_Width)
	{
		FreeBuffers();
		m_Width = width;
		m_Height = height;
		m_Buffer = reinterpret_cast<float*>(_aligned_malloc(m_Width*m_Height*sizeof(*m_Buffer), 32));
		m_SuperWidth = m_Width >> BLOCK_SHIFT;
		m_SuperHeight = m_Height >> BLOCK_SHIFT;
		m_SuperBuffer = new float[m_SuperWidth*m_SuperHeight];
	}

	memset(m_Buffer, 0, sizeof(float)*m_Width*m_Height);
	memset(m_SuperBuffer, 0, sizeof(float)*m_SuperWidth*m_SuperHeight);

	Matrix44 mat_view, mat_proj, mat_viewproj;
	CCamera tmp_cam = m_pRenderer->GetCamera();
	m_pRenderer->SetCamera(m_Camera);
	m_pRenderer->GetModelViewMatrix(reinterpret_cast<f32*>(&mat_view));
	m_pRenderer->GetProjectionMatrix(reinterpret_cast<f32*>(&mat_proj));
	mat_viewproj =	mat_view*mat_proj;
	mat_viewproj.Transpose();
	(Vec4 &)m_MatViewProj.m00 = (Vec4 &)mat_viewproj.m00;
	(Vec4 &)m_MatViewProj.m10 = (Vec4 &)mat_viewproj.m10;
	(Vec4 &)m_MatViewProj.m20 = (Vec4 &)mat_viewproj.m30;
	m_pRenderer->SetCamera(tmp_cam);
	m_NearZ = m_Camera.GetNearPlane();
}

void CWBufferCuller::AddRenderMesh(IRenderMesh *pRM, Matrix34A *pTranRotMatrix, IMaterial *pMaterial, bool bOutdoorOnly, bool bCompletelyInFrustum, bool bNoCull)
{
	FUNCTION_PROFILER_3DENGINE;
	if(!pMaterial)
		return;

	m_ObjectsWritten++;
	
	IRenderMesh::ThreadAccessLock lockrm(pRM);

	Matrix34 mat_complete =	m_MatViewProj * *pTranRotMatrix;

	pRM->LockForThreadAccess();
	uint32 vertex_count = pRM->GetVerticesCount();
	int32 vertex_size	= 0;
	const byte* pPos = pRM->GetPosPtr(vertex_size, FSL_READ);

	if (m_VertexCache.size() < vertex_count)
		m_VertexCache.resize(vertex_count);

	// Transform vertices
	for (uint32 i=0; i<vertex_count; i++)
	{
		m_VertexCache[i] = mat_complete * reinterpret_cast<const Vec3 &>(pPos[vertex_size * i]);
	}

	// Check if we need to do clipping
	if (!bCompletelyInFrustum)
	{
		bCompletelyInFrustum = true;
		for (uint32 i=0; i<vertex_count; i++)
		{
			if (m_VertexCache[i].z < m_NearZ)
			{
				bCompletelyInFrustum = false;
				break;
			}
		}
	}

	// Project vertices now if we don't need to clip
	if (bCompletelyInFrustum)
	{
		for (uint32 i=0; i<vertex_count; i++)
			PROJECT_VERTEX(m_VertexCache[i], m_VertexCache[i]);
	}

	PodArray<CRenderChunk> &Chunks = pRM->GetChunks();
	const uint16 *pIndices = pRM->GetIndexPtr(FSL_READ);
	pRM->UnLockForThreadAccess();
	for (int nChunkId=0; nChunkId<Chunks.Count(); nChunkId++)
	{
		CRenderChunk *pChunk = &Chunks[nChunkId];
		if (pChunk->m_nMatFlags & MTL_FLAG_NODRAW || !pChunk->pRE)
			continue;

		IShader *pShader = pMaterial->GetShaderItem(pChunk->m_nMatID).m_pShader;
		if (!pShader)
			continue;

		//ECull nCullMode = bNoCull ? eCULL_None : pShader->GetCull();
		ECull nCullMode = pShader->GetCull();

		if (bCompletelyInFrustum)
		{
			int last_index = pChunk->nFirstIndexId + pChunk->nNumIndices;
			for (int idx = pChunk->nFirstIndexId; idx < last_index; idx += 3)
			{
				Vec3 &v0 = m_VertexCache[pIndices[idx]];
				Vec3 &v1 = m_VertexCache[pIndices[idx+1]];
				Vec3 &v2 = m_VertexCache[pIndices[idx+2]];

				float area = (v1.x-v0.x) * (v2.y-v0.y) - (v2.x-v0.x) * (v1.y-v0.y);

				if (area > 0.0f)
				{
					if (nCullMode != eCULL_Front)
						DrawTriangle(v0, v1, v2);
				}
				else if (area < 0.0f)
				{
					
					if (nCullMode != eCULL_Back)
						DrawTriangle(v0, v2, v1);
				}
			}
		}
		else
		{
			int last_index = pChunk->nFirstIndexId + pChunk->nNumIndices;
			for (int idx = pChunk->nFirstIndexId; idx < last_index; idx += 3)
			{
				Vec3 &v0 = m_VertexCache[pIndices[idx]];
				Vec3 &v1 = m_VertexCache[pIndices[idx+1]];
				Vec3 &v2 = m_VertexCache[pIndices[idx+2]];

				float area = (v1 - v0).Cross(v2 - v0).Dot(v0);

				if (area > 0.0f)
				{
					if (nCullMode != eCULL_Front)
						ClipAndDrawTriangle(v0, v1, v2);
				}
				else if (area < 0.0f)
				{
					
					if (nCullMode != eCULL_Back)
						ClipAndDrawTriangle(v0, v2, v1);
				}
			}
		}
	}
}

void CWBufferCuller::AddOccluderPlane(Vec3 _vertices[4])
{
	Vec3 vertices[4];

	for (int i=0; i<4; i++)
		vertices[i] = m_MatViewProj * _vertices[i];
	
	ClipAndDrawTriangle(vertices[0], vertices[2], vertices[1]);
	ClipAndDrawTriangle(vertices[0], vertices[3], vertices[2]);
}

bool CWBufferCuller::IsObjectVisible(const AABB &_objBox, EOcclusionObjectType eOcclusionObjectType, float fDistance, uint32 *pRetVal) const
{
	FUNCTION_PROFILER_3DENGINE;
	m_ObjectsTested++;

	AABB objBox;

	objBox.min = _objBox.min - Vec3(BOX_EPSILON, BOX_EPSILON, BOX_EPSILON);
	objBox.max = _objBox.max + Vec3(BOX_EPSILON, BOX_EPSILON, BOX_EPSILON);

	Vec3 vertices[8];

	vertices[0] = m_MatViewProj * Vec3(objBox.min.x, objBox.min.y, objBox.min.z);
	vertices[1] = m_MatViewProj * Vec3(objBox.min.x, objBox.max.y, objBox.min.z);
	vertices[2] = m_MatViewProj * Vec3(objBox.max.x, objBox.min.y, objBox.min.z);
	vertices[3] = m_MatViewProj * Vec3(objBox.max.x, objBox.max.y, objBox.min.z);
	vertices[4] = m_MatViewProj * Vec3(objBox.min.x, objBox.min.y, objBox.max.z);
	vertices[5] = m_MatViewProj * Vec3(objBox.min.x, objBox.max.y, objBox.max.z);
	vertices[6] = m_MatViewProj * Vec3(objBox.max.x, objBox.min.y, objBox.max.z);
	vertices[7] = m_MatViewProj * Vec3(objBox.max.x, objBox.max.y, objBox.max.z);

	for (int i=0; i<8; i++)
	{
		if (vertices[i].z < m_NearZ)
			return true;
		PROJECT_VERTEX(vertices[i], vertices[i]);
	}

	Vec3 cam_pos = m_Camera.GetPosition();

	if (cam_pos.x > objBox.max.x)
	{
		if (TestQuad(vertices[2], vertices[3], vertices[7], vertices[6]))
			return true;
	}
	else if (cam_pos.x < objBox.min.x)
	{
		if (TestQuad(vertices[1], vertices[0], vertices[4], vertices[5]))
			return true;
	}

	if (cam_pos.y > objBox.max.y)
	{
		if (TestQuad(vertices[3], vertices[1], vertices[5], vertices[7]))
			return true;
	}
	else if (cam_pos.y < objBox.min.y)
	{
		if (TestQuad(vertices[0], vertices[2], vertices[6], vertices[4]))
			return true;
	}

	if (cam_pos.z > objBox.max.z)
	{
		if (TestQuad(vertices[5], vertices[4], vertices[6], vertices[7]))
			return true;
	}
	else if (cam_pos.z < objBox.min.z)
	{
		if (TestQuad(vertices[0], vertices[1], vertices[3], vertices[2]))
			return true;
	}

	m_ObjectsTestedAndRejected++;
	return false;
}

void CWBufferCuller::DrawDebug(int nStep)
{
	if (1 & nStep)
	{
		if (NULL == m_DebugBuffer)
			m_DebugBuffer = new uint8[m_Width*m_Height];

		for (int i=0, y=0; y<m_Height; ++y)
			for (int x=0; x<m_Width; ++x, ++i)
				m_DebugBuffer[i] = 2.0f / 255.0f < m_Buffer[i] ? static_cast<uint8>(2.0f/m_Buffer[i]) : 255;

		if (-1 != m_DebugTextureID)
			m_pRenderer->UpdateTextureInVideoMemory(m_DebugTextureID, m_DebugBuffer, 0, 0, m_Width, m_Height, eTF_L8);
		else
			m_DebugTextureID = m_pRenderer->DownLoadToVideoMemory(m_DebugBuffer, m_Width, m_Height, eTF_L8, eTF_L8, 1, false, FILTER_POINT);

		m_pRenderer->Draw2dImage(500.0f, 375.0f, 200.0f, 150.0f, m_DebugTextureID);
	}

	if (2 & nStep)
	{
		Vec3 viewspace_rectangle[6];
		Vec3 worldspace_rectangles[6];

		Matrix44 viewmat;
		Matrix44 invviewmat;
		CCamera tmp_cam = m_pRenderer->GetCamera();
		m_pRenderer->SetCamera(m_Camera);
		m_pRenderer->GetModelViewMatrix(reinterpret_cast<float*>(&viewmat));
		viewmat.Transpose();
		invviewmat = viewmat.GetInverted();
		m_pRenderer->SetCamera(tmp_cam);

		float horizontal_size = tan(0.5f*m_pRenderer->GetCamera().GetHorizontalFov());
		float vertical_size = tan(0.5f*m_pRenderer->GetCamera().GetFov());
		
		for (int i=0; i<6; ++i)
			viewspace_rectangle[i].z = -1.0f;

		float rectangle_width = 2.0f*horizontal_size / m_Width;
		float rectangle_height = 2.0f*vertical_size / m_Height;

		float bottom = -vertical_size + (0.5f - 0.5f*COVERAGE_DEBUG_RECTANGLE_SCALE)*rectangle_width;
		for (int rect=0, y=0; y<m_Height; ++y, bottom+=rectangle_height)
		{
			float left = -horizontal_size + (0.5f - 0.5f*COVERAGE_DEBUG_RECTANGLE_SCALE)*rectangle_width;
			for (int x=0; x<m_Width; ++x, ++rect, left+=rectangle_width)
			{
				if (m_Buffer[rect])
				{
					float rect_dist = 1.0f/m_Buffer[rect];

					viewspace_rectangle[0].x = rect_dist*left;
					viewspace_rectangle[0].y = rect_dist*bottom;
					viewspace_rectangle[0].z = -rect_dist;
					viewspace_rectangle[1].x = rect_dist*(left+COVERAGE_DEBUG_RECTANGLE_SCALE*rectangle_width);
					viewspace_rectangle[1].y = rect_dist*bottom;
					viewspace_rectangle[1].z = -rect_dist;
					viewspace_rectangle[2].x = rect_dist*(left+COVERAGE_DEBUG_RECTANGLE_SCALE*rectangle_width);
					viewspace_rectangle[2].y = rect_dist*(bottom+COVERAGE_DEBUG_RECTANGLE_SCALE*rectangle_height);
					viewspace_rectangle[2].z = -rect_dist;
					viewspace_rectangle[3].x = rect_dist*left;
					viewspace_rectangle[3].y = rect_dist*bottom;
					viewspace_rectangle[3].z = -rect_dist;
					viewspace_rectangle[4].x = rect_dist*(left+COVERAGE_DEBUG_RECTANGLE_SCALE*rectangle_width);
					viewspace_rectangle[4].y = rect_dist*(bottom+COVERAGE_DEBUG_RECTANGLE_SCALE*rectangle_height);
					viewspace_rectangle[4].z = -rect_dist;
					viewspace_rectangle[5].x = rect_dist*left;
					viewspace_rectangle[5].y = rect_dist*(bottom+COVERAGE_DEBUG_RECTANGLE_SCALE*rectangle_height);
					viewspace_rectangle[5].z = -rect_dist;

					for (int i=0; i<6; ++i)
						worldspace_rectangles[i] = invviewmat.TransformPoint(viewspace_rectangle[i]);

					uint32 color = static_cast<uint32>(2.0f*rect_dist);
					if (255 < color)
						color = 255;

					color |= color << 8 | color << 16 | 0xff000000;
					m_pRenderer->GetIRenderAuxGeom()->DrawTriangles(worldspace_rectangles, 6, ColorB(color));
				}
			}
		}
	}
}

void CWBufferCuller::ClipAndDrawTriangle(const Vec3 &v0, const Vec3 &v1, const Vec3 &v2)
{
	Vec3 p0, p1, p2;
	int mask = (v0.z > m_NearZ) + ((v1.z > m_NearZ) << 1) + ((v2.z > m_NearZ) << 2);

	if (mask == 7)
	{
		// All 3 vertices inside
		PROJECT_VERTEX(p0, v0);
		PROJECT_VERTEX(p1, v1);
		PROJECT_VERTEX(p2, v2);
		DrawTriangle(p0, p1, p2);
	}
	else if (mask & (mask-1))
	{
		// 2 vertices inside
		if (mask == 6)
			p0 = v0, p1 = v1, p2 = v2;
		else if (mask == 5)
			p0 = v1, p1 = v2, p2 = v0;
		else
			p0 = v2, p1 = v0, p2 = v1;

		Vec3 p01, p02;

		p01 = p1 + (p0 - p1) * ((m_NearZ - p1.z) / (p0.z - p1.z));
		p02 = p2 + (p0 - p2) * ((m_NearZ - p2.z) / (p0.z - p2.z));
		PROJECT_VERTEX(p1, p1);
		PROJECT_VERTEX(p2, p2);
		PROJECT_VERTEX(p01, p01);
		PROJECT_VERTEX(p02, p02);
		DrawTriangle(p01, p1, p2);
		DrawTriangle(p2, p02, p01);
	}
	else if (mask != 0)
	{
		// 1 vertex inside
		if (mask == 1)
			p0 = v0, p1 = v1, p2 = v2;
		else if (mask == 2)
			p0 = v1, p1 = v2, p2 = v0;
		else
			p0 = v2, p1 = v0, p2 = v1;
		
		p1 = p0 + (p1 - p0) * ((m_NearZ - p0.z) / (p1.z - p0.z));
		p2 = p0 + (p2 - p0) * ((m_NearZ - p0.z) / (p2.z - p0.z));
		PROJECT_VERTEX(p0, p0);
		PROJECT_VERTEX(p1, p1);
		PROJECT_VERTEX(p2, p2);
		DrawTriangle(p0, p1, p2);
	}
}

void CWBufferCuller::DrawTriangle(const Vec3 &v0, const Vec3 &v1, const Vec3 &v2)
{
	FUNCTION_PROFILER_3DENGINE;

	m_TrisWritten++;

	int minx = int(min(v0.x, min(v1.x, v2.x)));
	int maxx = int(max(v0.x, max(v1.x, v2.x))) + 1;
	int miny = int(min(v0.y, min(v1.y, v2.y)));
	int maxy = int(max(v0.y, max(v1.y, v2.y))) + 1;

	minx = max(minx, 0);
	maxx = min(maxx, m_Width);
	miny = max(miny, 0);
	maxy = min(maxy, m_Height);

	if (minx >= maxx || miny >= maxy)
		return;

	Plane p;
	p.n = (v1 - v0).Cross(v2 - v0);
	p.d = -p.n.Dot(v0);
	if (fabs(p.n.z) < 1e-6)
		return;
	float rnz = -1.0f/p.n.z;
	float zx = p.n.x*rnz;
	float zy = p.n.y*rnz;
	float zc = p.d*rnz;

	minx &= ~(BLOCK_SIZE - 1);
	miny &= ~(BLOCK_SIZE - 1);

	float x01 = v0.x - v1.x;
	float x12 = v1.x - v2.x;
	float x20 = v2.x - v0.x;

	float y01 = v0.y - v1.y;
	float y12 = v1.y - v2.y;
	float y20 = v2.y - v0.y;

	float c0 = x01*v0.y - y01*v0.x;
	float c1 = x12*v1.y - y12*v1.x;
	float c2 = x20*v2.y - y20*v2.x;

	float c0min = c0 - (x01 * (x01 > 0 ? 0 : BLOCK_SIZE-1) - y01 * (y01 > 0 ? BLOCK_SIZE-1 : 0));
	float c0max = c0 - (x01 * (x01 > 0 ? BLOCK_SIZE-1 : 0) - y01 * (y01 > 0 ? 0 : BLOCK_SIZE-1));

	float c1min = c1 - (x12 * (x12 > 0 ? 0 : BLOCK_SIZE-1) - y12 * (y12 > 0 ? BLOCK_SIZE-1 : 0));
	float c1max = c1 - (x12 * (x12 > 0 ? BLOCK_SIZE-1 : 0) - y12 * (y12 > 0 ? 0 : BLOCK_SIZE-1));

	float c2min = c2 - (x20 * (x20 > 0 ? 0 : BLOCK_SIZE-1) - y20 * (y20 > 0 ? BLOCK_SIZE-1 : 0));
	float c2max = c2 - (x20 * (x20 > 0 ? BLOCK_SIZE-1 : 0) - y20 * (y20 > 0 ? 0 : BLOCK_SIZE-1));

	for (int by = miny; by < maxy; by+=BLOCK_SIZE)
	{
		for (int bx = minx; bx < maxx; bx+=BLOCK_SIZE)
		{
			float *sup = m_SuperBuffer + m_SuperWidth*(by >> BLOCK_SHIFT) + (bx >> BLOCK_SHIFT);
			float z_test = zx*(bx + (zx > 0 ? BLOCK_SIZE-1 : 0)) + zy*(by + (zy > 0 ? BLOCK_SIZE-1 : 0)) + zc;
			if (*sup > z_test)
				continue;

			float *ptr = m_Buffer + m_Width*by + bx;

			float line0block = x01*by - y01*bx;
			float line1block = x12*by - y12*bx;
			float line2block = x20*by - y20*bx;

			if (line0block <= c0max && line1block <= c1max && line2block <= c2max)
			{
#if OC_SSE
				__m128 z_sup = _mm_set1_ps(FLT_MAX);

				__m128 coeff = _mm_set1_ps(zy);
				__m128 offset = _mm_set_ss(zx);
				__m128 tweak_coeff = _mm_set_ps(3.0f, 2.0f, 1.0f, 0.0f);
				__m128 z_current_tweak = _mm_shuffle_ps(offset, offset, _MM_SHUFFLE(0, 0, 0, 0));
#if 2 < BLOCK_SHIFT
				__m128 increment_coeff = _mm_set1_ps(4.0f);
				__m128 z_current_increment = _mm_mul_ps(z_current_tweak, increment_coeff);
#endif
				z_current_tweak = _mm_mul_ps(z_current_tweak, tweak_coeff);
				offset = _mm_mul_ss(offset, _mm_cvtepi32_ps(_mm_cvtsi32_si128(bx)));
				offset = _mm_add_ss(offset, _mm_set_ss(zc));
				offset = _mm_shuffle_ps(offset, offset, _MM_SHUFFLE(0, 0, 0, 0));
				offset = _mm_add_ps(offset, z_current_tweak);

				for (int y = by; y < by+BLOCK_SIZE; y++)
				{
					__m128 z_current = _mm_mul_ps(coeff, _mm_cvtepi32_ps(_mm_set1_epi32(y)));
					z_current = _mm_add_ps(z_current, offset);

					__m128 z_mem_values;

					z_mem_values = _mm_load_ps(ptr);
					z_mem_values = _mm_max_ps(z_mem_values, z_current);
					z_sup = _mm_min_ps(z_sup, z_mem_values);
					_mm_store_ps(ptr, z_mem_values);

#if 2 < BLOCK_SHIFT
					z_current = _mm_add_ps(z_current, z_current_increment);

					z_mem_values = _mm_load_ps(ptr+4);
					z_mem_values = _mm_max_ps(z_mem_values, z_current);
					z_sup = _mm_min_ps(z_sup, z_mem_values);
					_mm_store_ps(ptr+4, z_mem_values);
#endif

					ptr += m_Width;
				}
				z_sup = _mm_min_ps(z_sup, _mm_shuffle_ps(z_sup, z_sup, _MM_SHUFFLE(1, 0, 3, 2)));
				z_sup = _mm_min_ps(z_sup, _mm_shuffle_ps(z_sup, z_sup, _MM_SHUFFLE(2, 3, 0, 1)));
				_mm_store_ss(sup, z_sup);
#else
				float z_sup = FLT_MAX;

				for (int y = by; y < by+BLOCK_SIZE; y++)
				{
					float z_current = zx*bx + zy*y + zc;

					for (int x = 0; x < BLOCK_SIZE; x++)
					{
						ptr[x] = max(ptr[x], z_current);
						z_sup = min(z_sup, ptr[x]);
						z_current += zx;
					}

					ptr += m_Width;
				}

				*sup = z_sup;
#endif
			}
			else if (line0block <= c0min && line1block <= c1min && line2block <= c2min)
			{
#if OC_SSE
				__m128 z_sup = _mm_set1_ps(FLT_MAX);

				__m128 c0_mm = _mm_set1_ps(c0);
				__m128 c1_mm = _mm_set1_ps(c1);
				__m128 c2_mm = _mm_set1_ps(c2);

				__m128 coeff = _mm_set_ps(x20, x12, x01, zy);
				__m128 offset = _mm_set_ps(-y20, -y12, -y01, zx);
				__m128 tweak_coeff = _mm_set_ps(3.0f, 2.0f, 1.0f, 0.0f);
				__m128 z_current_tweak = _mm_shuffle_ps(offset, offset, _MM_SHUFFLE(0, 0, 0, 0));
				__m128 line0_tweak = _mm_shuffle_ps(offset, offset, _MM_SHUFFLE(1, 1, 1, 1));
				__m128 line1_tweak = _mm_shuffle_ps(offset, offset, _MM_SHUFFLE(2, 2, 2, 2));
				__m128 line2_tweak = _mm_shuffle_ps(offset, offset, _MM_SHUFFLE(3, 3, 3, 3));
#if 2 < BLOCK_SHIFT
				__m128 increment_coeff = _mm_set1_ps(4.0f);
				__m128 z_current_increment = _mm_mul_ps(z_current_tweak, increment_coeff);
				__m128 line0_increment = _mm_mul_ps(line0_tweak, increment_coeff);
				__m128 line1_increment = _mm_mul_ps(line1_tweak, increment_coeff);
				__m128 line2_increment = _mm_mul_ps(line2_tweak, increment_coeff);
#endif
				z_current_tweak = _mm_mul_ps(z_current_tweak, tweak_coeff);
				line0_tweak = _mm_mul_ps(line0_tweak, tweak_coeff);
				line1_tweak = _mm_mul_ps(line1_tweak, tweak_coeff);
				line2_tweak = _mm_mul_ps(line2_tweak, tweak_coeff);
				offset = _mm_mul_ps(offset, _mm_cvtepi32_ps(_mm_set1_epi32(bx)));
				offset = _mm_add_ss(offset, _mm_set_ss(zc));
				for (int y = by; y < by+BLOCK_SIZE; y++)
				{
					__m128 line_values = _mm_mul_ps(coeff, _mm_cvtepi32_ps(_mm_set1_epi32(y)));
					line_values = _mm_add_ps(line_values, offset);
					__m128 z_current = _mm_shuffle_ps(line_values, line_values, _MM_SHUFFLE(0, 0, 0, 0));
					z_current = _mm_add_ps(z_current, z_current_tweak);
					__m128 line0 = _mm_shuffle_ps(line_values, line_values, _MM_SHUFFLE(1, 1, 1, 1));
					line0 = _mm_add_ps(line0, line0_tweak);
					__m128 line1 = _mm_shuffle_ps(line_values, line_values, _MM_SHUFFLE(2, 2, 2, 2));
					line1 = _mm_add_ps(line1, line1_tweak);
					__m128 line2 = _mm_shuffle_ps(line_values, line_values, _MM_SHUFFLE(3, 3, 3, 3));
					line2 = _mm_add_ps(line2, line2_tweak);

					__m128 mask, z_mem_values;

					mask = _mm_cmple_ps(line0, c0_mm);
					mask = _mm_and_ps(mask, _mm_cmple_ps(line1, c1_mm));
					mask = _mm_and_ps(mask, _mm_cmple_ps(line2, c2_mm));

					z_mem_values = _mm_load_ps(ptr);
					z_mem_values = _mm_max_ps(z_mem_values, _mm_and_ps(z_current, mask));
					z_sup = _mm_min_ps(z_sup, z_mem_values);
					_mm_store_ps(ptr, z_mem_values);

#if 2 < BLOCK_SHIFT
					z_current = _mm_add_ps(z_current, z_current_increment);
					line0 = _mm_add_ps(line0, line0_increment);
					line1 = _mm_add_ps(line1, line1_increment);
					line2 = _mm_add_ps(line2, line2_increment);

					mask = _mm_cmple_ps(line0, c0_mm);
					mask = _mm_and_ps(mask, _mm_cmple_ps(line1, c1_mm));
					mask = _mm_and_ps(mask, _mm_cmple_ps(line2, c2_mm));

					z_mem_values = _mm_load_ps(ptr+4);
					z_mem_values = _mm_max_ps(z_mem_values, _mm_and_ps(z_current, mask));
					z_sup = _mm_min_ps(z_sup, z_mem_values);
					_mm_store_ps(ptr+4, z_mem_values);
#endif
					ptr += m_Width;
				}
				z_sup = _mm_min_ps(z_sup, _mm_shuffle_ps(z_sup, z_sup, _MM_SHUFFLE(1, 0, 3, 2)));
				z_sup = _mm_min_ps(z_sup, _mm_shuffle_ps(z_sup, z_sup, _MM_SHUFFLE(2, 3, 0, 1)));
				_mm_store_ss(sup, z_sup);
#else
				float z_sup = FLT_MAX;

				for (int y = by; y < by+BLOCK_SIZE; y++)
				{
					float line0 = x01 * y - y01 * bx;
					float line1 = x12 * y - y12 * bx;
					float line2 = x20 * y - y20 * bx;
					float z_current = zx*bx + zy*y + zc;

					for (int x = 0; x < BLOCK_SIZE; x++)
					{
						if (line0 <= c0 && line1 <= c1 &&	line2 <= c2)
							ptr[x] = max(ptr[x], z_current);
						z_sup = min(z_sup, ptr[x]);

						line0 -= y01;
						line1 -= y12;
						line2 -= y20;
						z_current += zx;
					}

					ptr += m_Width;
				}

				*sup = z_sup;
#endif
			}
		}
	}
}

bool CWBufferCuller::TestQuad(const Vec3 &v0, const Vec3 &v1, const Vec3 &v2, const Vec3 &v3) const
{
	FUNCTION_PROFILER_3DENGINE;

	m_TrisTested++;

	int minx = int(min(min(v0.x, v1.x), min(v2.x, v3.x))) - 1;
	int maxx = int(max(max(v0.x, v1.x), max(v2.x, v3.x))) + 2;
	int miny = int(min(min(v0.y, v1.y), min(v2.y, v3.y))) - 1;
	int maxy = int(max(max(v0.y, v1.y), max(v2.y, v3.y))) + 2;

	minx = max(minx, 0);
	maxx = min(maxx, m_Width);
	miny = max(miny, 0);
	maxy = min(maxy, m_Height);

	if (minx >= maxx || miny >= maxy)
		return false;

	Plane p;
	p.n = (v1 - v0).Cross(v2 - v0);
	p.d = -p.n.Dot(v0);
	if (fabs(p.n.z) < 1e-6)
		return false;
	float rnz = -1.0f/p.n.z;
	float zx = p.n.x*rnz;
	float zy = p.n.y*rnz;
	float zc = p.d*rnz;

	float x01 = v0.x - v1.x;
	float x12 = v1.x - v2.x;
	float x23 = v2.x - v3.x;
	float x30 = v3.x - v0.x;

	float y01 = v0.y - v1.y;
	float y12 = v1.y - v2.y;
	float y23 = v2.y - v3.y;
	float y30 = v3.y - v0.y;

	float c0 = x01 * (v0.y + (x01 > 0 ? .5f : -.5f)) - y01 * (v0.x + (y01 > 0 ? -.5f : .5f));
	float c1 = x12 * (v1.y + (x12 > 0 ? .5f : -.5f)) - y12 * (v1.x + (y12 > 0 ? -.5f : .5f));
	float c2 = x23 * (v2.y + (x23 > 0 ? .5f : -.5f)) - y23 * (v2.x + (y23 > 0 ? -.5f : .5f));
	float c3 = x30 * (v3.y + (x30 > 0 ? .5f : -.5f)) - y30 * (v3.x + (y30 > 0 ? -.5f : .5f));

	minx &= ~(BLOCK_SIZE - 1);
	miny &= ~(BLOCK_SIZE - 1);

	float c0min = c0 - (x01 * (x01 > 0 ? 0 : BLOCK_SIZE-1) - y01 * (y01 > 0 ? BLOCK_SIZE-1 : 0));
	float c0max = c0 - (x01 * (x01 > 0 ? BLOCK_SIZE-1 : 0) - y01 * (y01 > 0 ? 0 : BLOCK_SIZE-1));

	float c1min = c1 - (x12 * (x12 > 0 ? 0 : BLOCK_SIZE-1) - y12 * (y12 > 0 ? BLOCK_SIZE-1 : 0));
	float c1max = c1 - (x12 * (x12 > 0 ? BLOCK_SIZE-1 : 0) - y12 * (y12 > 0 ? 0 : BLOCK_SIZE-1));

	float c2min = c2 - (x23 * (x23 > 0 ? 0 : BLOCK_SIZE-1) - y23 * (y23 > 0 ? BLOCK_SIZE-1 : 0));
	float c2max = c2 - (x23 * (x23 > 0 ? BLOCK_SIZE-1 : 0) - y23 * (y23 > 0 ? 0 : BLOCK_SIZE-1));

	float c3min = c3 - (x30 * (x30 > 0 ? 0 : BLOCK_SIZE-1) - y30 * (y30 > 0 ? BLOCK_SIZE-1 : 0));
	float c3max = c3 - (x30 * (x30 > 0 ? BLOCK_SIZE-1 : 0) - y30 * (y30 > 0 ? 0 : BLOCK_SIZE-1));

	for (int by = miny; by < maxy; by+=BLOCK_SIZE)
	{
		for (int bx = minx; bx < maxx; bx+=BLOCK_SIZE)
		{
			float *sup = m_SuperBuffer + m_SuperWidth*(by >> BLOCK_SHIFT) + (bx >> BLOCK_SHIFT);
			float z_test = zx*(bx + (zx > 0 ? BLOCK_SIZE-1 : 0)) + zy*(by + (zy > 0 ? BLOCK_SIZE-1 : 0)) + zc;
			if (*sup > z_test)
				continue;

			float *ptr = m_Buffer + m_Width*by + bx;

			float line0block = x01*by - y01*bx;
			float line1block = x12*by - y12*bx;
			float line2block = x23*by - y23*bx;
			float line3block = x30*by - y30*bx;

			if (line0block <= c0max && line1block <= c1max && line2block <= c2max && line3block <= c3max)
			{
				for (int y = by; y < by+BLOCK_SIZE; y++)
				{
					float z_current = zx*bx + zy*y + zc;

					for (int x = 0; x < BLOCK_SIZE; x++)
					{
						if (ptr[x] <= z_current)
							return true;
						z_current += zx;
					}

					ptr += m_Width;
				}
			}
			else if (line0block <= c0min && line1block <= c1min && line2block <= c2min && line3block <= c3min)
			{
#if OC_SSE
				__m128 c0_mm = _mm_set1_ps(c0);
				__m128 c1_mm = _mm_set1_ps(c1);
				__m128 c2_mm = _mm_set1_ps(c2);
				__m128 c3_mm = _mm_set1_ps(c3);

				__m128 coeff = _mm_set_ps(x30, x23, x12, x01);
				__m128 offset = _mm_set_ps(-y30, -y23, -y12, -y01);
				__m128 z_current_coeff = _mm_set1_ps(zy);
				__m128 z_current_offset = _mm_set1_ps(zx);

				__m128 tweak_coeff = _mm_set_ps(3.0f, 2.0f, 1.0f, 0.0f);
				__m128 z_current_tweak = z_current_offset;
				__m128 line0_tweak = _mm_shuffle_ps(offset, offset, _MM_SHUFFLE(0, 0, 0, 0));
				__m128 line1_tweak = _mm_shuffle_ps(offset, offset, _MM_SHUFFLE(1, 1, 1, 1));
				__m128 line2_tweak = _mm_shuffle_ps(offset, offset, _MM_SHUFFLE(2, 2, 2, 2));
				__m128 line3_tweak = _mm_shuffle_ps(offset, offset, _MM_SHUFFLE(3, 3, 3, 3));
#if 2 < BLOCK_SHIFT
				__m128 increment_coeff = _mm_set1_ps(4.0f);
				__m128 z_current_increment = _mm_mul_ps(z_current_tweak, increment_coeff);
				__m128 line0_increment = _mm_mul_ps(line0_tweak, increment_coeff);
				__m128 line1_increment = _mm_mul_ps(line1_tweak, increment_coeff);
				__m128 line2_increment = _mm_mul_ps(line2_tweak, increment_coeff);
				__m128 line3_increment = _mm_mul_ps(line3_tweak, increment_coeff);
#endif
				z_current_tweak = _mm_mul_ps(z_current_tweak, tweak_coeff);
				line0_tweak = _mm_mul_ps(line0_tweak, tweak_coeff);
				line1_tweak = _mm_mul_ps(line1_tweak, tweak_coeff);
				line2_tweak = _mm_mul_ps(line2_tweak, tweak_coeff);
				line3_tweak = _mm_mul_ps(line3_tweak, tweak_coeff);
				__m128 bx_mm = _mm_cvtepi32_ps(_mm_set1_epi32(bx));
				offset = _mm_mul_ps(offset, bx_mm);
				z_current_offset = _mm_mul_ps(z_current_offset, bx_mm);
				z_current_offset = _mm_add_ps(z_current_offset, _mm_set1_ps(zc));
				z_current_offset = _mm_add_ps(z_current_offset, z_current_tweak);

				for (int y = by; y < by+BLOCK_SIZE; y++)
				{
					__m128 y_mm = _mm_cvtepi32_ps(_mm_set1_epi32(y));
					__m128 line_values = _mm_mul_ps(coeff, y_mm);
					__m128 z_current = _mm_mul_ps(z_current_coeff, y_mm);
					line_values = _mm_add_ps(line_values, offset);
					z_current = _mm_add_ps(z_current, z_current_offset);

					__m128 line0 = _mm_shuffle_ps(line_values, line_values, _MM_SHUFFLE(0, 0, 0, 0));
					line0 = _mm_add_ps(line0, line0_tweak);
					__m128 line1 = _mm_shuffle_ps(line_values, line_values, _MM_SHUFFLE(1, 1, 1, 1));
					line1 = _mm_add_ps(line1, line1_tweak);
					__m128 line2 = _mm_shuffle_ps(line_values, line_values, _MM_SHUFFLE(2, 2, 2, 2));
					line2 = _mm_add_ps(line2, line2_tweak);
					__m128 line3 = _mm_shuffle_ps(line_values, line_values, _MM_SHUFFLE(3, 3, 3, 3));
					line3 = _mm_add_ps(line3, line3_tweak);

					__m128 mask, z_mem_values;

					mask = _mm_cmple_ps(line0, c0_mm);
					mask = _mm_and_ps(mask, _mm_cmple_ps(line1, c1_mm));
					mask = _mm_and_ps(mask, _mm_cmple_ps(line2, c2_mm));
					mask = _mm_and_ps(mask, _mm_cmple_ps(line3, c3_mm));

					z_mem_values = _mm_load_ps(ptr);
					mask = _mm_and_ps(mask, _mm_cmple_ps(z_mem_values, z_current));
					mask = _mm_or_ps(mask, _mm_shuffle_ps(mask, mask, _MM_SHUFFLE(1, 0, 3, 2)));
					mask = _mm_or_ps(mask, _mm_shuffle_ps(mask, mask, _MM_SHUFFLE(2, 3, 0, 1)));
					if (reinterpret_cast<int&>(mask))
						return true;

#if 2 < BLOCK_SHIFT
					z_current = _mm_add_ps(z_current, z_current_increment);
					line0 = _mm_add_ps(line0, line0_increment);
					line1 = _mm_add_ps(line1, line1_increment);
					line2 = _mm_add_ps(line2, line2_increment);
					line3 = _mm_add_ps(line3, line3_increment);

					mask = _mm_cmple_ps(line0, c0_mm);
					mask = _mm_and_ps(mask, _mm_cmple_ps(line1, c1_mm));
					mask = _mm_and_ps(mask, _mm_cmple_ps(line2, c2_mm));
					mask = _mm_and_ps(mask, _mm_cmple_ps(line3, c3_mm));

					z_mem_values = _mm_load_ps(ptr+4);
					mask = _mm_and_ps(mask, _mm_cmple_ps(z_mem_values, z_current));
					mask = _mm_or_ps(mask, _mm_shuffle_ps(mask, mask, _MM_SHUFFLE(1, 0, 3, 2)));
					mask = _mm_or_ps(mask, _mm_shuffle_ps(mask, mask, _MM_SHUFFLE(2, 3, 0, 1)));
					if (reinterpret_cast<int&>(mask))
						return true;
#endif
					ptr += m_Width;
				}
#else
				for (int y = by; y < by+BLOCK_SIZE; y++)
				{
					float line0 = x01 * y - y01 * bx;
					float line1 = x12 * y - y12 * bx;
					float line2 = x23 * y - y23 * bx;
					float line3 = x30 * y - y30 * bx;
					float z_current = zx*bx + zy*y + zc;

					for (int x = 0; x < BLOCK_SIZE; x++)
					{
						if (line0 <= c0 && line1 <= c1 && line2 <= c2 && line3 <= c3)
						{
							if (ptr[x] <= z_current)
								return true;
						}

						line0 -= y01;
						line1 -= y12;
						line2 -= y23;
						line3 -= y30;
						z_current += zx;
					}

					ptr += m_Width;
				}
#endif
			}
		}
	}

	return false;
}

void CWBufferCuller::GetMemoryUsage(ICrySizer *pSizer) const
{
	SIZER_COMPONENT_NAME(pSizer, "CoverageBuffer");
	pSizer->AddObject(this, sizeof(CWBufferCuller));
	pSizer->AddObject(m_Buffer, sizeof(float)*m_Width*m_Height);
	pSizer->AddObject(m_SuperBuffer, sizeof(float)*m_SuperWidth*m_SuperHeight);
	pSizer->AddContainer(m_VertexCache);
}

#endif // WIN32
#endif // #if OCCLUSIONCULLER == CWBufferCuller